是的，今天仍是動態規劃系列。今天來討論哩扣上面跟整除有關的動態規劃問題吧～

Exercise 35: Leetcode 650 - 2 Keys Keyboard

題目連結

https://leetcode.com/problems/2-keys-keyboard/

題目敘述

一開始螢幕上有個 "A" 字元。你有兩個按鈕，每次可以「複製全部」或是「貼上前次複製的東西」。請問至少要按幾次按鈕才能夠湊齊 n 個字元呢？

解題思考

我們用 C 代表複製 P 代表貼上。那麼輸入序列一定可以被分成「複製+若干次貼上」的許多段落。考慮最後一段，貼上若干次以後湊齊 n 個字元。因此此次複製的東西一定是 n 的因數。所以呢，我們想要作的事情就是找出那個因數 d 使得 dp(n) = dp(d) + 1次複製 + (n/d-1) 次貼上。

這題時間複雜度比較精妙一些。其實我們只需要計算 n 的所有因數的狀態就行了，其實可以做到 n 的O(因數個數*質因數個數)時間。只是因為這題範圍實在太小，所以可以很輕鬆地考慮所有 n。

參考程式碼 (Python3)

class Solution:
    def minSteps(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[1] = 0
        for k in range(2, n+1):
            dp[k] = k
            for i in range(2, k):
                if k % i == 0:
                    dp[k] = min(dp[k], dp[i] + (k//i))
        return dp[n]

Exercise 36: Leetcode 368 - Largest Divisible Subset

題目連結

https://leetcode.com/problems/largest-divisible-subset/

題目敘述

給你 n 個相異的數字。請找出最大的子集合，使得集合內任何兩個數字 Si, Sj 要嘛 Si % Sj == 0 要嘛 Sj % Si == 0。最後輸出這個子集合。

解題思考

根據集合條件，答案的集合內元素一定是從小到大一個整除下一個。因此我們可以作 LIS 類似的概念：先把所有數字由小到大排列好。然後對於每一個數字，找看看前面能夠整除它的數字中，最長的那串到底有多長就行了。

這題的範圍好像很小，我們可以輕易地把整串數字通通拷貝出來，時間複雜度應該會是個 n^3。但寫起來世界無敵短。而且 python 很好用。

參考程式碼 (Python3)

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        dp = [[x] for x in nums]
        nums.sort()
        for i in range(len(nums)):
            for j in range(0, i):
                if nums[i] % nums[j] == 0 and len(dp[i]) < len(dp[j]) + 1:
                    dp[i] = dp[j] + [nums[i]]
        return max(dp, key=len, default=[])

快要追上去年21天的紀錄了呢。希望今年可以成功寫完30天。好的我們明天見～